package _dp_base;

import java.util.HashMap;
import java.util.Map;

/**
 * 1218. 最长定差子序列
 */
public class No1218 {
    private int[] arr;
    private int difference;
    private int[] cache;

    /**
     * 1. 递归（超时）
     */
    public int longestSubsequence1(int[] arr, int difference) {
        this.arr = arr;
        this.difference = difference;
        int n = arr.length;
        cache = new int[n];

        int answer = 0;
        for (int i = 0; i < n; i++) {
            answer = Math.max(dfs(i), answer);
        }
        return answer;
    }

    private int dfs(int i) {
        if (cache[i] != 0) return cache[i];
        int curLen = 1;
        for (int j = 0; j < i; j++) {
            if (arr[i] - arr[j] == difference) {
                int preLen = dfs(j);
                curLen = Math.max(preLen + 1, curLen);
            }
        }
        return cache[i] = curLen;
    }


    /**
     * 2. 迭代（超时）
     */
    public int longestSubsequence2(int[] arr, int difference) {
        int n = arr.length;
        int[] f = new int[n];

        int answer = 0;
        for (int i = 0; i < n; i++) {
            int curLen = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i] - arr[j] == difference) {
                    int preLen = f[j];
                    curLen = Math.max(preLen + 1, curLen);
                }
            }
            f[i] = curLen;
            answer = Math.max(f[i], answer);
        }
        return answer;
    }


    /**
     * 3. 剪枝（超时）
     */
    public int longestSubsequence3(int[] arr, int difference) {
        int n = arr.length;
        int[] f = new int[n];

        int answer = 0;
        for (int i = 0; i < n; i++) {
            int curLen = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] == arr[i] - difference) {
                    curLen = f[j] + 1;
                    break;
                }
            }
            f[i] = curLen;
            answer = Math.max(f[i], answer);
        }
        return answer;
    }


    /**
     * 4. 哈希表降维
     */
    public int longestSubsequence4(int[] arr, int difference) {
        Map<Integer, Integer> f = new HashMap<>();

        int answer = 0;
        for (int arrI : arr) {
            int arrJ = arrI - difference;
            int curLen = f.getOrDefault(arrJ, 0) + 1;
            f.put(arrI, curLen);
            answer = Math.max(f.get(arrI), answer);
        }
        return answer;
    }
}
